//A robot is located at the top-left corner of a m x n grid (marked 'Start' in t
//he diagram below). 
//
// The robot can only move either down or right at any point in time. The robot 
//is trying to reach the bottom-right corner of the grid (marked 'Finish' in the d
//iagram below). 
//
// Now consider if some obstacles are added to the grids. How many unique paths 
//would there be? 
//
// An obstacle and space is marked as 1 and 0 respectively in the grid. 
//
// 
// Example 1: 
//
// 
//Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
//Output: 2
//Explanation: There is one obstacle in the middle of the 3x3 grid above.
//There are two ways to reach the bottom-right corner:
//1. Right -> Right -> Down -> Down
//2. Down -> Down -> Right -> Right
// 
//
// Example 2: 
//
// 
//Input: obstacleGrid = [[0,1],[0,0]]
//Output: 1
// 
//
// 
// Constraints: 
//
// 
// m == obstacleGrid.length 
// n == obstacleGrid[i].length 
// 1 <= m, n <= 100 
// obstacleGrid[i][j] is 0 or 1. 
// 
// Related Topics 数组 动态规划 
// 👍 550 👎 0


package leetcode.editor.cn;

import java.util.Arrays;

//Java：Unique Paths II
class P63UniquePathsIi {
    public static void main(String[] args) {
        Solution solution = new P63UniquePathsIi().new Solution();
//        System.out.println(solution.uniquePathsWithObstacles(new int[][]{{0, 1}, {0, 0}}));
        System.out.println(solution.uniquePathsWithObstacles(new int[][]{{1}}));
        System.out.println(solution.uniquePathsWithObstacles(new int[][]{{0, 0, 0}, {0, 1, 0}, {0, 0, 0}}));
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        int[][] memo;

        public int uniquePathsWithObstacles1(int[][] matrix) {
            return path(0, 0, matrix);

        }

        public int uniquePathsWithObstacles(int[][] obstacleGrid) {
            int[][] ints = new int[obstacleGrid.length][obstacleGrid[0].length];
            return uniquePathsWithObstacles(obstacleGrid, obstacleGrid.length - 1, obstacleGrid[0].length - 1, ints);
        }

        public int uniquePathsWithObstacles(int[][] obstacleGrid, int x, int y, int[][] memo) {
            if (x < 0 || y < 0) {
                return 0;
            }
            if (memo[x][y] != 0) {
                return memo[x][y];
            }
            if (x == 0 && y == 0 && obstacleGrid[x][y] == 0) {
                return 1;
            }
            if (obstacleGrid[x][y] == 1) {
                return 0;
            }
            memo[x][y] += uniquePathsWithObstacles(obstacleGrid, x - 1, y, memo) + uniquePathsWithObstacles(obstacleGrid, x, y - 1, memo);
            return memo[x][y];
        }

        //1.自顶向下迭代
        private int path(int x, int y, int[][] matrix) {
            memo = new int[matrix.length][matrix[0].length];
            for (int i = 0; i < memo.length; i++) {
                if (matrix[i][0] == 1) {
                    break;
                }
                memo[i][0] = 1;
            }
            for (int j = 0; j < memo[0].length; j++) {
                if (matrix[0][j] == 1) {
                    break;
                }
                memo[0][j] = 1;
            }
            for (int i = 1; i < matrix.length; i++) {
                for (int j = 1; j < matrix[0].length; j++) {
                    if (matrix[i][j] == 1) {
                        matrix[i][j] = 0;
                    } else {
                        memo[i][j] = memo[i - 1][j] + memo[i][j - 1];
                    }

                }
            }
            return memo[matrix.length - 1][matrix[0].length - 1];
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}